/*
110. 平衡二叉树

给定一个二叉树，确定它是高度平衡的。

对于这个问题，一棵高度平衡二叉树的定义是：

    一棵二叉树中每个节点的两个子树的深度相差不会超过 1。

案例 1:

给出二叉树 [3,9,20,null,null,15,7]:

    3
   / \
  9  20
    /  \
   15   7

返回 true 。

案例 2:

给出二叉树 [1,2,2,3,3,null,null,4,4]:

       1
      / \
     2   2
    / \
   3   3
  / \
 4   4

返回 false 。
*/

/* 对于一个节点a
    它的孩子节点是2a+1 和 2a+2
    它的兄弟是 a^1
    它的兄弟的孩子节点是 2*(a^1)+1和2*(a^1)+2
    当它自己没有孩子,而兄弟的孩子有孩子节点时,它不是平衡2x树
    *错误解法*
*/
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution
{
private:
    bool testNode(TreeNode *node)
    {
        if(node->left != NULL) {
            if(node->left->left != NULL ||
               node->left->right != NULL) {
                return false;
            }
        }
        if(node->right != NULL) {
            if(node->right->left != NULL ||
               node->right->left != NULL) {
                return false;
            }
        }
        return true;
    }

public:
    bool isBalanced(TreeNode *root)
    {
        TreeNode *left = root->left;
        TreeNode *right = root->right;
        if(left == NULL && right == NULL) {
            /* 叶子 */
            return true;
        } else {
            if(left == NULL) {
                return testNode(right);
            } else if(right == NULL) {
                return testNode(left);
            } else {
                if(isBalanced(left)) {
                    return isBalanced(right);
                }
            }
        }
        return false;
    }
};

/*
遍历这颗树,找到最短深度,和最长深度
两者相差1以上,则不是.
错误解答
*/

class Solution
{
private:
    int min;
    int max;
    int updateDeep(int deep)
    {
        if(min == -1 || min > deep) min = deep;
        if(max == -1 || max < deep) max = deep;
        if(max - min > 1) return 1;
        return 0;
    }
    bool findx(TreeNode *n, int deep)
    {
        if(!n->right || !n->left) {
            if(updateDeep(deep)) {
                return false;
            }
        }
        if(n->left && !findx(n->left, deep + 1)) {
            return false;
        }
        if(n->right && !findx(n->right, deep + 1)) {
            return false;
        }
        return max - min <= 1;
    }

public:
    bool isBalanced(TreeNode *root)
    {
        min = max = -1;
        if(!root) return true;
        return findx(root, 0);
    }
};


class Solution
{
public:
    bool isBalanced(TreeNode *root)
    {
        int height = 0;
        return isBalancedUtil(root, height);
    }

    bool isBalancedUtil(TreeNode *root, int &height)
    {
        if(root == NULL) {
            height = 0;
            return true;
        }
        int  lh = 0, rh = 0;
        bool isLeft = isBalancedUtil(root->left, lh);
        bool isRight = isBalancedUtil(root->right, rh);
        height = (lh > rh ? lh : rh) + 1;
        return (abs(lh - rh) <= 1 && isLeft && isRight);
    }
};